class Solution 
{
public:
    string reorganizeString(string s) 
    {
        int n=s.size();
        int hash[26]={0};
        for(auto&c:s) hash[c-'a']++;
        char c;int maxcount=0;
        for(int i=0;i<26;i++) 
        {
            if(hash[i]>0)
            {
                if(hash[i]>maxcount)
                {
                    maxcount=hash[i];
                    c=i+'a';
                }
            }
        }
        if(maxcount>(n+1)/2) return "";
        int index=0;
        while(maxcount--)
        {
            s[index]=c;
            index+=2;
        }
        for(char ch='a';ch<='z';ch++)
        {
            if(hash[ch-'a']>0&&ch!=c)
            {
                int count=hash[ch-'a'];
                while(count--)
                {
                    if(index>=n) index=1;
                    s[index]=ch;
                    index+=2;
                }
            }
        }
        return s;

    }
};